/*
题目: Pow(x,n)
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

https://leetcode.cn/problems/powx-n/
 */
public class MyPower {
    public double myPow(double x, int n) {
        // 快速幂, 这要根据 n 的次来判断
        long m = n; // 防溢出
        return m >= 0 ? f(x, m) : 1.0 / f(x, -m);
    }

    private double f(double x, long n) {
        // 10101 = 10000 + 100 + 1, 我们只需要去根据二进制中的1来计算结果
        // 对于 n 的二进制进行快速幂运算
        double src = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                src *= x;
            }

            x *= x;
            n >>= 1;
        }
        return src;
    }
}
